#ifndef CLINKEDLIST_H_
#define CLINKEDLIST_H_

#include <stdio.h>
#include "cobject.h"

/**
 * TItem - item of linked list
 */
template<typename T> struct TItem {
  TItem() :
    value(value) {
  }
  TItem(T value) :
    value(value) {
  }
  T value;
  TItem* next;
};

/**
 * CLinkedList - class representing linear linked list (LLS)
 * @author Michal Rost
 * @date 10.01.2007
 */
template<typename T> class CLinkedList : public CObject {
public:

  /**
   * CLinkedList - create empty LLS
   */
  CLinkedList() {
    init();
  }
  //-------------------------------------------------------------------------

  /**
   * CLinkedList - create LLS from pointer to LLS head
   * @param h pointer to the first item (head) of linked list
   */
  CLinkedList(const TItem<T>* h) {
    init();
    insertListToEnd(h);
  }
  //-------------------------------------------------------------------------

  /**
   * CLinkedList - copy constructor (creates a deep copy of LLS)
   * @param l
   */
  CLinkedList(const CLinkedList<T> &l) {
    copyFrom(l);
  }
  //-------------------------------------------------------------------------

  /**
   * operator= - assignment of LLS (deep copy)
   * @param l
   */
  CLinkedList<T>& operator =(const CLinkedList<T> &l) {
    free();
    copyFrom(l);
    return *this;
  }
  //-------------------------------------------------------------------------

  /**
   * ~CLinkedList() - destroys linked list
   */
  ~CLinkedList() {
    free();
  }
  //-------------------------------------------------------------------------

  /**
   * insertListToBeg - inserts copy of given LLS before beginning of LLS
   * @param l LLS which will be inserted before beginning
   */
  void insertListToBeg(const CLinkedList<T> &l) {
    insertListToBeg(l.getHead());
  }
  //-------------------------------------------------------------------------

  /**
   * insertListToEnd - inserts copy of given LLS after end of LLS
   * @param l LLS which will be inserted after end
   */
  void insertListToEnd(const CLinkedList<T> &l) {
    insertListToEnd(l.getHead());
  }
  //-------------------------------------------------------------------------

  /**
   * insertListToBeg - inserts copy of given LLS before beginning of LLS
   * @param h head of LLS which will be inserted after end
   */
  void insertListToBeg(TItem<T>* h) {

    // Test head
    if (!h) {
      return;
    }

    // Copy head of inserted LLS
    TItem<T>* first = new TItem<T> ;
    first->value = h->value;
    TItem<T>* prev = first;

    // Move to next item of inserted LLS
    TItem<T>* tmp = h->next;

    // Copy items of inserted LLS
    while (tmp) {
      TItem<T>* tmpNew = new TItem<T> ;
      tmpNew->value = tmp->value;
      prev->next = tmpNew;
      prev = tmpNew;
      tmp = tmp->next;
    }

    // Insert head of this LLS after end of inserted (copied) LLS
    prev->next = head;
    head = first;
  }
  //-------------------------------------------------------------------------

  /**
   * insertListToEnd - inserts copy of given LLS after end of LLS
   * @param h head of LLS which will be inserted after end
   */
  void insertListToEnd(TItem<T>* h) {
    TItem<T>* tmp = h;
    while (tmp) {
      insertToEnd(tmp->value);
      tmp = tmp->next;
    }
  }
  //-------------------------------------------------------------------------

  /**
   * insertToBeg - inserts new item before beginning of LLS
   * @param value value of new item
   */
  void insertToBeg(T value) {

    // Create new item and insert it before head
    TItem<T>* tmp = new TItem<T> ;
    tmp->value = value;
    tmp->next = head;

    // New head
    head = tmp;

    // Find tail of LLS
    if (!tail) {
      tail = findTail();
    }
  }
  //-------------------------------------------------------------------------

  /**
   * insertToEnd - inserts new item after end of LLS
   * @param value value of new item
   */
  void insertToEnd(T value) {

    // New item
    TItem<T>* tmp = new TItem<T> ;
    tmp->value = value;
    tmp->next = NULL;

    // If LLS is empty last item (tail) is also head, return
    if (!head) {
      head = tmp;
      tail = head;
      return;
    }

    // Find tail of LLS
    if (!tail) {
      tail = findTail();
    }

    // Insert new item after tail and mark it as tail
    tail->next = tmp;
    tail = tail->next;
  }
  //-------------------------------------------------------------------------

  /**
   * removeFromBeg - removes item from the beginning of LLS
   */
  void removeFromBeg() {
    TItem<T>* tmp = head;
    head = head->next;
    delete tmp;
  }
  //-------------------------------------------------------------------------

  /**
   * removeFromEnd - removes item from the end of LLS
   */
  void removeFromEnd() {

    // If LLS is empty, return
    if (!head) {
      return;
    }

    // If LSS contains only head, delete it and return
    if (!head->next) {
      delete head;
      head = NULL;
      return;
    }

    // Find two last items
    TItem<T>* prev = head;
    TItem<T>* tmp = head;
    while (tmp->next) {
      prev = tmp;
      tmp = tmp->next;
    }

    // Delete last item and mark previous item as tail
    prev->next = NULL;
    delete tmp;
    tail = prev;
  }
  //-------------------------------------------------------------------------

  /**
   * clear - deletes LSS
   */
  void clear() {
    free();
  }
  //-------------------------------------------------------------------------

  /**
   * findTail - finds last item (tail) of LLS
   * @return tail
   */
  TItem<T>* findTail() const {

    // If LLS is empty, return
    if (!head) {
      return NULL;
    }

    // Find LLS tail
    TItem<T>* tmp = head;
    while (tmp->next) {
      tmp = tmp->next;
    }
    return tmp;
  }
  //-------------------------------------------------------------------------

  /**
   * getHead - returns LLS head
   * @return head
   */
  TItem<T>* getHead() const {
    return head;
  }
  //-------------------------------------------------------------------------

  /**
   * getClassName - returns classname
   * @return classname
   */
  static std::string getClassName() {
    return "CLinkedList";
  }
  //-------------------------------------------------------------------------
protected:
  TItem<T>* head;
  TItem<T>* tail;

  /**
   * init - inits empty LLS
   */
  void init() {
    head = NULL;
    tail = NULL;
  }
  //-------------------------------------------------------------------------

  /**
   * free - deletes LLS
   */
  void free() {
    TItem<T>* tmp = head;

    while (tmp) {
      TItem<T>* prev = tmp;
      tmp = tmp->next;
      delete prev;
    }
    head = NULL;
    tail = NULL;
  }
  //-------------------------------------------------------------------------

  /**
   * copyFrom - copies given LSS
   * @param l
   */
  void copyFrom(const CLinkedList<T> &l) {
    insertListToEnd(l);
  }
  //-------------------------------------------------------------------------
};

#endif
